import java.util.Random;

public class Solution {

  // 快速排序 1：基本快速排序

  /**
   * 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序
   */
  private static final int INSERTION_SORT_THRESHOLD = 7;

  private static final Random RANDOM = new Random();

  public int[] sortArray(int[] nums) {
    int len = nums.length;
    quickSort(nums, 0, len - 1);
    return nums;
  }

  private void quickSort(int[] nums, int left, int right) {
    // 小区间使用插入排序
    if (right - left <= INSERTION_SORT_THRESHOLD) {
      insertionSort(nums, left, right);
      return;
    }

    int pIndex = partition(nums, left, right);
    quickSort(nums, left, pIndex - 1);
    quickSort(nums, pIndex + 1, right);
  }

  private int partition(int[] nums, int left, int right) {
    int randomIndex = RANDOM.nextInt(right - left + 1) + left;
    swap(nums, left, randomIndex);

    // 左边的值设置为 基准值pivot
    int pivot = nums[left];
    // 设置指针
    int lt = left;
    // 循环不变量：
    // all in [left + 1, lt] < pivot
    // all in [lt + 1, i) >= pivot
    // 循环遍历nums
    for (int i = left + 1; i <= right; i++) {
      if (nums[i] < pivot) {
        // 指针右移
        lt++;
        swap(nums, i, lt);
      }
    }
    swap(nums, left, lt);
    return lt;
  }

  private void swap(int[] nums, int index1, int index2) {
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
  }

  /**
   * 对数组 nums 的子区间 [left, right] 使用插入排序
   *
   * @param nums  给定数组
   * @param left  左边界，能取到
   * @param right 右边界，能取到
   */
  private void insertionSort(int[] nums, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
      int temp = nums[i];
      int j = i;
      while (j > left && nums[j - 1] > temp) {
        nums[j] = nums[j - 1];
        j--;
      }
      nums[j] = temp;
    }
  }
}
